package subject.huisu;

public class exist {

    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w]; // 标记访问过的位置

        // 尝试以每个网格位置为起点
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (check(board, visited, i, j, word, 0)) {
                    return true; // 找到单词立即返回
                }
            }
        }
        return false; // 所有起点都找不到
    }

    public boolean check(char[][] board, boolean[][] visited,
                         int i, int j, String s, int k) {
        // 1. 当前字符不匹配：直接失败
        if (board[i][j] != s.charAt(k)) return false;

        // 2. 已匹配完整单词：成功
        if (k == s.length() - 1) return true;

        visited[i][j] = true; // 标记当前单元格已访问

        // 定义四个移动方向：右、左、下、上
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;

        // 3. 尝试所有相邻位置
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];

            // 检查新位置是否在网格内且未访问
            if (newi >= 0 && newi < board.length &&
                    newj >= 0 && newj < board[0].length) {

                if (!visited[newi][newj]) {
                    // 递归搜索下一个字符
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) { // 找到完整单词
                        result = true;
                        break; // 提前结束
                    }
                }
            }
        }

        visited[i][j] = false; // 回溯：取消标记
        return result;
    }
}
